home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
PsL Monthly 1993 December
/
PSL Monthly Shareware CD-ROM (December 1993).iso
/
prgmming
/
dos
/
c
/
snippet.exe
/
LASORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-07-19
|
12KB
|
238 lines
/*********************************************************************/
/* */
/* This Program Written by Paul Edwards. */
/* */
/*********************************************************************/
/*********************************************************************/
/* */
/* licorice all sort - an O(N) sort program. Version 1.31 */
/* */
/* This program takes the following parameters: */
/* 1) base - A pointer to the start of your data */
/* 2) n - number of elements to be sorted */
/* 3) size - size of elements being sorted */
/* 4) offset - number of bytes into the record */
/* */
/* Designed to be much like C's builtin qsort, this program sorts */
/* into ascending order an array base[0]...base[n-1] of objects */
/* size size. (not a typo). */
/* */
/* After my last aborted attempt at creating an original sort */
/* program, here is a new one. It is called lasort, short for */
/* licorice all sort. */
/* */
/* To sort an array of character strings, you first start off */
/* looking at the first byte. You create a table of statistics */
/* (UCHAR_MAX entries) so that you know how many A's ther are etc. */
/* */
/* It then once again traverses the list, knowing where to put */
/* each element that is out of order. */
/* */
/* This code is dedicated to the public domain. Do with it what */
/* you will, but seeing as I invented it, it shall be known */
/* hereafter as licorice all sort, and not by any other name. */
/* The unusual name was suggested by my father, who preferred it */
/* to death sort. Also, a catchy name helps to make a sort */
/* popular (ala bubble sort). */
/* */
/* If you would like to contact me about this program, I normally */
/* hang out on a bulletin board called Paragon, in Sydney, */
/* Australia. Fidonet address: 3:712/502 */
/* */
/* licorice - I don't like it either. */
/* */
/* Written on 03-Oct-1989. */
/* */
/* Copyright 1989 Paul Edwards. */
/* */
/* Dedicated to my American friend Dan Malcolm, convinced */
/* that Australians never write public domain software <grin>. */
/* */
/* Version 1.3 enhancement. When you have less than or equal to */
/* RETIME records to sort, use Radix Exchange Sort instead. */
/* When you have less than or equal to INTIME records to sort, use */
/* Insertion Sort instead. */
/* */
/* Version 1.31 fixed up void *, char *, unsigned char * */
/* */
/*********************************************************************/
/* RETIME, INTIME are machine dependant, find values that suit you */
/* best. List of possible optimum times for different machines: */
/* IBM XT compatible: RETIME 46, INTIME 7 */
#define RETIME 46 /* when radix is better than licorice */
#define INTIME 7 /* when insertion sort is better than resort */
#define MAX 300 /* maximum length of strings to be sorted */
static char temp[MAX]; /* temporary storage for swap */
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <stdlib.h>
/*********************************************************************/
/* */
/* insertion sort - start from the bottom element (which is a */
/* sorted array of length 1), then every time you move up one */
/* element, you move it down (swapping with all elements below it) */
/* until it is in its sorted position. */
/* */
/*********************************************************************/
void insort(void *base, int n, int size, int offset)
{
register int j,rc,i;
for (i=0;i<n;i++) /* moving up one element */
{
for (j=i;j>0;j--) /* move down until in sorted order */
{
rc = memcmp((unsigned char *)base+j*size+offset,
(unsigned char *)base+(j-1)*size+offset,size-offset);
if (rc < 0)
{
/* swapping elements along the way */
memcpy(temp,(unsigned char *)base+j*size,size);
memcpy((unsigned char *)base+j*size,
(unsigned char *)base+(j-1)*size,size);
memcpy((unsigned char *)base+(j-1)*size,temp,size);
}
else break;
}
}
return;
}
/*********************************************************************/
/* */
/* radix exchange sort. view one bit at a time, getting all '1' */
/* bits up the top, and all the '0' bits down the bottom. */
/* */
/*********************************************************************/
void resort(void *base, int n, int size, int offset)
{
int bytesin; /* no of bytes into the string */
int bitsin; /* no of bits into the byte */
int p; /* bottom element number */
int q; /* top element number */
register unsigned char mask = 0x80; /* bit we are interested in */
if (n <= 1) return; /* we have finished this sub-sort if we have
one or less elements to sort */
bytesin = offset / CHAR_BIT; /* work out how many bytes we are
into the element by dividing by the number of bits we are
into the element by the number of bits in a byte */
if (bytesin == size) return; /* we have just passed the length of the
data */
bitsin = offset % CHAR_BIT; /* no of bits into the byte */
mask = mask >> bitsin; /* mask masks the bit we are interested in */
p = 0; /* low element starts at 0 */
q = n-1; /* high element starts at n-1 */
while (p <= q) /* until all swaps have been done */
{
while (((*((unsigned char *)base+p*size+bytesin) & mask) == 0)
&& (p < n)) p++; /* p will move up until it finds a bit that
is not 0 (or until it reaches the top) */
/* q moves down until if finds a bit that is 0
(or until it reaches the bottom) */
while ((q >= 0) &&
((*((unsigned char *)base+q*size+bytesin) & mask) != 0)) q--;
if (p < q) /* p has a 1 bit and q has a 0 bit, so swap */
{
memcpy(temp,(unsigned char *)base+p*size,size);
memcpy((unsigned char *)base+p*size,
(unsigned char *)base+q*size,size);